package binarySearch;

/**
 * @author pengfei.hpf
 * @date 2020/3/11
 * @verdion 1.0.0
 */
public class ShipWithinDays {
    public int shipWithinDays(int[] weights, int D){
        if(weights == null || weights.length == 0){
            return 0;
        }
        int l = getMax(weights);
        int r = getSum(weights) + 1;
        while(l < r){
            int mid = l + (r - l)/2;
            if(canFinished(weights, mid, D)){
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean canFinished(int[] weights, int cap, int D){
        int i = 0;
        for(int d = 0; d < D; d ++){
            int perCap = cap;
            while(i < weights.length && perCap - weights[i] >= 0){
                perCap = perCap - weights[i];
                i++;
                if(i == weights.length){
                    return true;
                }
            }
        }
        return false;
    }

    private int getMax(int[] weights){
        int max = 0;
        for(int i: weights){
            max = Math.max(max, i);
        }
        return max;
    }


    private int getSum(int[] weights){
        int sum = 0;
        for(int i: weights){
            sum += i;
        }
        return sum;
    }
}
